package com.zhangx.datastructure.tree;

/**
 * 线索二叉树
 * P191
 */
public class PointerTree {

    Node head;

    Node[] tree;

    int r,n;

    Node pre;

    static class Node{
        String data;
//        类型 0 子节点 1 前驱
        int leftType;
//        类型 0 子节点 1 后继
        int rightType;
        Node left;
        Node right;

        Node(String data,Node left,Node right){
            this.data = data;
            this.left = left;
            this.right = right;
        }
    }

    public PointerTree(){
//        初始化数据
        Node i = new Node("i",null,null);
        Node j = new Node("j",null,null);
        Node k = new Node("k",null,null);

        Node h = new Node("h",null,k);
        Node f = new Node("f",i,null);
        Node g = new Node("g",null,j);

        Node d = new Node("d",h,null);
        Node e = new Node("e",null,null);
        Node b = new Node("b",d,e);
        Node c = new Node("c",f,g);
        Node a = new Node("a",b,c);

        tree = new Node[11];
        tree[0] = a;
        tree[1] = b;
        tree[2] = c;
        tree[3] = d;
        tree[4] = e;
        tree[5] = f;
        tree[6] = g;
        tree[7] = h;
        tree[8] = i;
        tree[9] = j;
        tree[10] = k;

        this.r = 0;
        this.n = tree.length;

        head.left = tree[r];
        head.rightType = 1;
        head.right = tree[n-1];

    }

    /**
     * 线索化-建立前驱/后继
     * @param p
     */
    public void inThreading(Node p){

        if (null == p){
            return;
        }

        inThreading(p.left);
        if (p.left == null){
            p.leftType = 1;
//            前驱
            p.left = pre;
        }
//        只能找前节点的，因为当前还不知道p的后继是谁，只知道自己是pre 的后继
        if (pre.right == null){
            pre.rightType = 1;
//            后继
            pre.right = p;
        }
        pre = p;
        System.out.println(p.data);
        inThreading(p.right);

    }

    public void inOrderTraverse(Node n){
//        todo 线索二叉树搜索？？？
        Node p = n.left;//根节点
        while (p != n){

        }

    }

    public static void main(String[] args) {
        PointerTree pointerTree = new PointerTree();
//        建立一次线索后续都可以用
        pointerTree.inThreading(pointerTree.tree[pointerTree.r]);

        pointerTree.inOrderTraverse(pointerTree.head);
    }
}
